/*
 * @Author: liusheng
 * @Date: 2022-06-26 11:22:31
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-26 11:28:30
 * @Description: 剑指 Offer II 080. 含有 k 个元素的组合
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
  剑指 Offer II 080. 含有 k 个元素的组合
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

 

示例 1:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
示例 2:

输入: n = 1, k = 1
输出: [[1]]
 

提示:

1 <= n <= 20
1 <= k <= n
 

注意：本题与主站 77 题相同： https://leetcode-cn.com/problems/combinations/

通过次数14,417   提交次数17,279
 */

#include "header.h"

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        allsubSet(res,n,k,1,{});
        return res;
    }
private:
    void allsubSet(vector<vector<int>> & subs,int n,int k,int cur,vector<int> prefix)
    {
        // 剪枝：prefix 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
        if ((prefix.size() + (n - cur + 1)) < k)
        {
            return;
        }

        if (k == prefix.size())
        {
            subs.push_back(prefix);
            return;
        }

        //this can not be put ahead the above
        // if (cur > n)
        // {
        //     return;
        // }

        prefix.push_back(cur);
        allsubSet(subs,n,k,cur + 1,prefix);
        prefix.pop_back();
        allsubSet(subs,n,k,cur + 1,prefix);
    }
};
